Algorithm: Shunting-yard (Steps)

We previously established the core structures of the Shunting-yard Algorithm—the Operator Stack and the Output List—which are essential for managing the order of tokens and resolving precedence. To perform the conversion of an expression like the A + B * C, we must define the precise, rule-based steps for handling every token encountered in the input stream.

The algorithm processes the Infix expression from left to right, applying these rules based on the token type:

• 1. Operands (e.g., A, B, 10)
  • Operands require no special ordering control; they are immediately appended to the Output List.
  • Action: Append to output.
• 2. Operators (+, -, *, /)
  • This is the most critical step, where the Operator Stack uses the FILO principle to enforce precedence and associativity.
  • The Comparison Loop: While the stack is not empty, the operator at top is not a left parenthesis, AND the top operator has higher or equal precedence than the current input operator:
    • Pop the operator from the stack and append it to the Output List.
  • Final Action: Push the current input operator onto the stack.
• 3. Parentheses (Grouping)
  • Parentheses temporarily override standard precedence rules, ensuring grouped expressions are processed first.
  • Left Parenthesis (: Always pushed onto the Operator Stack.
  • Right Parenthesis ):
    • Pop operators from the stack and append them to the Output List until the matching Left Parenthesis is found.
    • Pop and discard the matching ( (do not send it to the Output List). If the stack runs empty without finding a (, the input expression was unbalanced.
• 4. End of Input
  • Once the entire input expression has been processed, pop any remaining operators from the Operator Stack and append them to the Output List. This clears the stack and completes the final Postfix expression.